package com.platform.modules.alg.alglib.poj3630;

public class Poj3630 {
    public String output = "";

    private int maxn = 1005; // 最多 10000 个字符串，每个字符串最多 10 位
    private int maxz = 10; // 不同字符个数，例如数字10，小写字母26
    int trie[][];
    boolean end[]; // 标识单词结束
    int n; // 字符串数
    int tot; // 下标

    boolean insert(String s) { // 将字符串s插入到字典树中
        int len = s.length();
        int p = 1;
        for (int i = 0; i < len; i++) {
            int ch = s.charAt(i) - '0'; // 转换成数字
            if (trie[p][ch] == 0)
                trie[p][ch] = ++tot; // 记录下标
            else if (i == len - 1) // 字符串处理完毕，仍不空，说明该串是其它串的前缀
                return true;
            p = trie[p][ch];
            if (end[p])
                return true;
        }
        end[p] = true; // 标记单词结束
        return false;
    }

    public String cal(String input) {
        int T;
        boolean ans;
        String s;
        String[] line = input.split("\n");
        T = Integer.parseInt(line[0]);
        int count = 1;
        while (T-- > 0) {
            trie = new int[maxn][maxz];
            end = new boolean[maxn];
            tot = 1;
            ans = false;
            n = Integer.parseInt(line[count++]);
            for (int i = 1; i <= n; i++) {
                s = line[count++];
                if (ans)
                    continue;
                if (insert(s)) // 不能立即结束，仍要读取 n 个串
                    ans = true;
            }
            if (ans)
                output += "NO\n"; // 有前缀输出 NO
            else
                output += "YES\n";
        }
        return output;
    }
}
